<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <title>Document</title>
</head>

<body>
  <script>
    //合并数组函数
    // 空间复杂度O(n)是辅助空间大小
    function merge(arr1, arr2) {
      let res = [];
      while (arr1.length && arr2.length) {
        if (arr1[0] > arr2[0]) {
          res.push(arr2.shift());
        } else {
          res.push(arr1.shift());
        }
      }
      return res.concat(arr1, arr2);
    }
    //归并排序
    function MergeSort(arr) {
      if (arr.length == 1) return arr;
      let mid = Math.floor(arr.length / 2);
      let arr1 = arr.slice(0, mid);
      let arr2 = arr.slice(mid);
      return merge(MergeSort(arr1), MergeSort(arr2));
    }
    console.log(MergeSort([2, 5, 3, 1, 6, 4, 2])); //[1, 2, 2, 3, 4, 5, 6]
  </script>

  <script>
    function myMerge(arr1, arr2) {
      let res = [];
      while (arr1.length && arr2.length) {
        if (arr1[0] > arr2[0]) {
          res.push(arr2.shift());
        } else {
          res.push(arr1.shift());
        }
      }
      return [...res, ...arr1, ...arr2];
    }
    function myMergeSort(array) {
      if (array.length === 1) return array;
      let middle = Math.floor(array.length / 2);
      let arr1 = array.slice(0, middle);
      let arr2 = array.slice(middle);
      return myMerge(myMergeSort(arr1), myMergeSort(arr2S));
    }
  </script>
</body>

</html>